#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
using namespace std;
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> v(m + 1, vector<int>(n + 2, 1000000));
        for (auto& e : v[0]) e = 0;
        for (int i = 1;i < m + 1;i++)
            for (int j =1;j < n + 1;j++)
            {
                v[i][j] = min(min(v[i - 1][j], v[i - 1][j - 1]), v[i - 1][j + 1]) + matrix[i - 1][j - 1];
            }
        int Min = v[m][1];
        for (auto& e : v[m]) Min = min(Min, e);
        return Min;
    }
};
class Solution123
{
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
    {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> v(m + 1, vector<int>(n + 1, 0));
        v[0][1] = 1;
        for (int i = 1;i < m + 1;i++)
            for (int j = 1;j < n + 1;j++)
            {
                if (obstacleGrid[i - 1][j - 1] == 0)
                    v[i][j] = v[i - 1][j] + v[i][j - 1];
                else
                    v[i][j] = 0;
            }
        return v[m][n];
    }
};

int main()
{
    vector<vector<int>> v = { {2,1,3},{6,5,4},{7,8,9} };
    Solution().minFallingPathSum(v);
    int arr[10] = { 0 };

	return 0;
}